We initiate the study of quantum algorithms for optimizing approximately convex functions. This achieves a polynomial quantum speedup compared to the best-known classical algorithms. As an application, we give a quantum algorithm for zeroth-order stochastic convex bandits with \tilde{O}(n {5}\log {2} T) regret, an exponential speedup in T compared to the classical \Omega(\sqrt{T}) lower bound. Technically, we achieve quantum speedup in n by exploiting a quantum framework of simulated annealing and adopting a quantum version of the hit-and-run walk. Our speedup in T for zeroth-order stochastic convex bandits is due to a quadratic quantum speedup in multiplicative error of mean estimation.